package com.zjw.algorithm.ready1;

import java.util.Arrays;

public class _快速排序2巩固 {

    public static void main(String[] args) {
        int[] arr = {5,1,1,2,0,0};
        new _快速排序2巩固().qSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }


    public void gSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }


        int mid = (start + end) >> 1;

        gSort(arr, start, mid);
        gSort(arr, mid + 1, end);

        //arr[start~mid]
        //arr[mid+1,end]

        int[] help = new int[end - start + 1];
        int lp = start;
        int rp = mid + 1;

        int count = 0;
        while (lp <= mid && rp <= end) {
            if (arr[lp] > arr[rp]) {
                help[count++] = arr[rp];
                rp++;
            } else {
                help[count++] = arr[lp];
                lp++;
            }
        }

        while (lp <= mid) {
            help[count++] = arr[lp++];
        }
        while (rp <= end) {
            help[count++] = arr[rp++];
        }

        System.arraycopy(help, 0, arr, start, end - start + 1);
    }

    public void qSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int lp = start - 1;
        int rp = end + 1;
        int povit = arr[(rp + lp) >> 1];


        while (lp < rp) {
            do {
                lp++;
            } while (arr[lp] < povit);


            do {
                rp--;
            } while (arr[rp] > povit);


            if (lp < rp) {
                int temp = arr[lp];
                arr[lp] = arr[rp];
                arr[rp] = temp;
            }
        }


        qSort(arr, start, rp);
        qSort(arr, rp + 1, end);
    }
}
